1. Field of the Invention
This invention relates generally to evaluation of mathematical functions of many variables, and more specifically to a volummetric linear interpolation process for approximating the value of a continuous multivariable function.
2. Description of the Prior Art
Many modern-day processes require the evaluation of one or more mathematical functions. These functions frequently involve a multiplicity of variables interrelated by relatively complex mathematical expressions. Oftentimes, the overall efficiency of a process is determined by the relative ease or difficulty with which a function may be evaluated. For instance, in the field of color imaging, it is often desired to convert a color image from a first color space to a second color space. The first color space may be for an image representation stored in a computer file, and the second color space may be for specification of color created on paper by means of printer inks.
During the implementation of a process, it is generally more important to provide an efficient function evaluation technique, as opposed to providing a function evaluation technique optimized for maximum accuracy. For example, during the process of color image conversion, a quick, expedient evaluation of color image functions is much more important than a completely accurate representation of the converted color image. Efficiency is of paramount importance in this context because a common design goal of many image processing systems is to provide real-time processing capability. Accuracy is not a critical design parameter because the human eye can compensate for minor imaging errors. The characteristics of human visual perception generally allow for the existence of a known bounded error in image rendering. Although the importance of efficiency relative to accuracy has been described in conjunction with color imaging systems, a similar situation exists across a broad spectrum of other process applications as well.
In some process applications, the output of a function may be sampled, but the function itself is unknown. For example, consider the conversion of an image from the color space of a computer file to the surface of a newspaper. The actual colors produced by the printing ink interacting with the paper are difficult or impossible to accurately quantify. The factors resulting in the appearance of a given color on paper are represented by an unknown function, even though the value of the function can be sampled at various intervals. In this scenario, an accurate representation of the imaging information is not at all critical, and emphasis may instead be placed on data processing speed.
Many existing processes involve mathematical functions having extensive domains. It is generally impractical to sample the output of the function at all possible sample values. For example, FIG. 1 illustrates the domain of a mathematical function representing the color of an object in the context of a color image processing system. State of the art color imaging systems represent a color image as a regular array of spots, generally referred to as pixels. Each pixel is assigned a color represented by the coordinates of the color in a three dimensional space. In an additive color environment (i.e., a cathode-ray tube display), any color may be represented by a given combination of the three primary colors of red, green, and blue. With reference to FIG. 1, the value of red may be represented along the X axis 12, green along the Y axis 14, and blue along the Z axis 16. Each coordinate may be of arbitrary precision, but coordinates are generally represented using 8-bit values. In this manner, each pixel may be assigned one of 2.sup.24 different colors. Therefore, the domain of the mathematical function representing pixel color is quite extensive.
The mathematical function accepts input values within the domain of the function, and produces output values corresponding to the input values. The sequence of mathematical operations carried out by the function are determined by the process to be implemented. To print a color image displayed on a cathode-ray tube, the image must be converted from additive to subtractive form. As previously described, the cathode-ray tube image is stored as a pixel-by-pixel representation specifying particular quantities of the colors red, green, and blue. For subtractive color applications, such as printing, the three primary colors are magenta, yellow, and cyan (blue-green), with black used as an additional or optional color for increased density (darkness) or decreased total ink usage. Accordingly, a function must be determined for the purpose of converting pixel color representations into known quantities of colored printer inks, typically with the amount expressed as an integer in the range of 0 to 255 for each of cyan, yellow, magenta, and black. The function accepts input values for the variables red, green, and blue, and produces output values which represent quantities of magenta, yellow, cyan, and black. Other color spaces in use as either input or output spaces include the colormetric spaces which represent color based on the tristimulus values that represent a standard observer as defined by the Commission Internationale de l'Eclairage. CIE L.sup.* a.sup.* b.sup.*, CIE L.sup.* u.sup.* v.sup.*, and CIE XYZ are three such spaces.
For many processes, it is highly impractical to define a function in analytical form. In the context of color image conversion, it would be very difficult to develop a working analytical model for the purpose of converting a cathode-ray tube image representation into a form suitable for color printing on newspaper media. If the printer inks offered a perfectly linear response, and if the paper was perfectly white, then the function for the conversion of the color image could be specified analytically. However, as a practical matter, the inks have a nonlinear response, and the paper is off-white. Consequently, the print function is best represented by using measurements accumulated for a plurality of print samples. There are 2.sup.24 points in the function domain which could be sampled, so it would be prohibitively time-consuming and storage intensive to measure and store all of these values. Rather, the function may be approximated using a smaller set of measured values (sample points ), and using interpolation to compute the approximate values for all of the other domain values.
One advantageous interpolation technique is known as volummetric linear interpolation. In the context of three-dimensional space, one of two techniques is usually employed to implement volummetric linear interpolation. The first technique is trilinear interpolation, and the second is tetrahedral interpolation. Tetrahedral interpolation is often selected in preference to other methods of approximating a function, such as trilinear interpolation, because tetrahedral interpolation requires fewer arithmetic operations to compute an approximation. The reduced number of steps required to execute tetrahedral interpolation has important practical consequences, in that less hardware is required, and the computational steps may be implemented faster and more efficiently.
Volummetric linear interpolation is implemented by selecting a plurality of sample points from the domain of a function. These points may be chosen at regularly-spaced intervals, as illustrated in FIG. 1. The domain of the mathematical function depicted in FIG. 1 is three-dimensional, with the result that the selected sample points form an array of geometrical volumes. Samples are taken at points 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, and 48. In this manner, the sample points form a rectangular grid throughout the domain of the function. The rectangular grid is comprised of a plurality of rectangular volumes 10.
In the case of tetrahedral interpolation, the domain of the function is divided into a plurality of tetrahedral volumes. The process of dividing the function domain in this manner is often a two-step procedure. Typically, the domain is first divided into rectangular solids as shown in FIG. 1, and then each of the rectangular solids so created is then subdivided into a plurality of tetrahedra.
FIG. 2 sets forth an illustrative example of subdividing a part of a function domain into tetrahedral volumes. A rectangular solid 10 is shown, corresponding to any one of the rectangular solids of FIG. 1. The rectangular solid 10 is subdivided into five tetrahedra 200, 202, 204, 206, and 208. Although the geometrical configuration of FIG. 2 illustrates the division of a rectangular volume into five tetrahedra, it is also possible to divide the rectangular volume into another number of tetrahedral structures. For example, the rectangular solids are often divided into six or twelve tetrahedra. One technique for subdividing the rectangular volume involves positioning six tetrahedra within the volume such that all six tetrahedra have a common base point at a corner of the rectangular solid. In this manner, all of the tetrahedra share a common edge along a diagonal of the rectangular volume. Methods, such as those described above, for dividing the domain of a function into geometrical volumes are well-known to those skilled in the art.
FIG. 3 is a perspective view illustrating the geometrical structure of a tetrahedron shown in FIG. 2. The tetrahedron 200 is a geometric solid having four planar faces 302,304,306, and 308, six edges a--a', b--b', c--c', d--d', e--e', and f--f', and four vertices 310,312,314, and 316.
To approximate the value v of the function at any arbitrarily selected point palong the function domain, the tetrahedron containing the selected point must be determined. The function values vat the four vertices 310,312,314, and 316 of the selected tetrahedron are sampled, and a standard three dimensional linear interpolation procedure is applied to the function values v to calculate an approximation for the function value v at the point p. The numerical constants required to implement the linear interpolation procedure such as the vertex coordinates and the corresponding function values are typically stored in one or more interpolation tables. In this manner, it is not necessary to obtain sample values for the function value v at all points along the function domain.
For a function of n variables at k+1&gt; n+l points, the function having m components, the standard linear interpolation procedure requires the performance of k+l multiplication steps and k addition steps for each of the m components of F. This totals (k+l)m multiplication operations and km addition operations. The performance of each of these mathematical operations consumes valuable hardware resources, and increases the time required to calculate an approximation. Consequently, it would be very desirable to reduce the overall number of operations required to implement volummetric linear interpolation. Multiplication steps should be avoided wherever possible, as these steps are much more expensive to implement than additions. Accordingly, it would be especially desirable to reduce the number of multiplication operations required.
The interpolation tables employed by existing volummetric interpolation methods must be stored in a memory device such as Random-Access Memory (RAM). These tables often occupy large blocks of memory space. Therefore, it would be desirable to reduce the size of the required interpolation tables in order to conserve valuable memory space.
A method of computing a tetrahedral interpolation function is described in "Color Correction Technique for Hard Copies by 4-Neighbors Interpolation Method", Journal of Imaging Science and Technology, Vol. 36, No. 1, Jan.-Feb. 1992, by Katsuhiro Kanamori and Kiroaki Kotera. This method discloses ##EQU2## to compute an approximation for the function value [c, m, y] which corresponds to the colors cyan, magenta and yellow, respectively.
The above formula is only applicable in the case of a function having both a three-dimensional input and a three-dimensional output. Quite frequently, however, it is desired to convert a standard Red-Green-Blue (RGB) video image into a Cyan-Magenta-Yellow-Black (CMYK) printed image. Alternatively, it may be desired to process image information received from a plurality of electromagnetic sensors, wherein each sensor is responsive to a different range of frequencies in the electromagnetic spectrum. If the output of each sensor is conceptualized as representing a given dimension, such an imaging system may require the performance of calculations in a number of dimensions greater than three. What is needed is a function approximation method which is capable of being utilized in conjunction with multidimensional functions where the domain inputs, range outputs or both, represent three or more dimensions.